#include <iostream>
#include <algorithm>

using namespace std;

const int N = 1010;
int w[N], v[N];
int f[N];

int main()
{
    int n, m;
    cin >> n >> m;
    for (int i = 1; i <= n; ++i)
    {
        cin >> v[i] >> w[i];
    }
    //朴素做法
    // f[i][j] = max(f[i - 1][j], f[i - 1][j - v[i] * k] + w[i] * k), k = 0 , 1,  2, ....
    
    // for (int i = 1; i <= n; ++i)
    // {
    //     for (int j = 0; j <= m; ++j)
    //     {
    //         for (int k = 0; k * v[i] <= j; ++k)
    //         {
    //             f[i][j] = max(f[i][j], f[i - 1][j - v[i] * k] + k * w[i]);
    //         }
    //     }
    // }

    //优化
    // f[i][j] = max(f[i - 1][j], f[i - 1][j - v[i] * k] + w[i] * k), k = 0 , 1,  2, ....

    // f[i][j - v[i]] = max (f[i - 1][j - v[i]* k] + w[i] * (k - 1)) k =0, 1, 2

    // f[i][j]  = max (f[i - 1][j], f[i][j - v[i]] + w[i]);

    // for (int i = 1; i <= n; ++i)
    // {
    //     for (int j = 0; j <= m; ++j)
    //     {
    //         f[i][j] = f[i - 1][j];
    //         if (j >= v[i])
    //         {
    //             f[i][j] = max(f[i][j], f[i][j - v[i]] + w[i]);
    //         }
    //     }
    // }
    //滚动数组, 空间优化
    for (int i = 1; i <= n; ++i)
    {
        for (int j = v[i]; j <= m; ++j)
        {
            f[j] = max(f[j], f[j - v[i]] + w[i]);
        }
    }
    cout << f[m];
    return 0;
}
